Vés al contingut

Algorisme recursiu

De la Viquipèdia, l'enciclopèdia lliure

Un algorisme recursiu és aquell que fa ús de la recursivitat. En la pràctica, és un algorisme implementat en una funció que es crida a si mateixa. Li cal una condició de parada per a no entrar en un bucle infinit. Alguns algorismes recursius es poden reescriure com algorismes iteratius.

Alguns exemples de recursivitat:

  • En un text:
Per a saber què és la recursivitat, primer s'ha de saber què és la recursivitat.
Què és GNU? → GNU No és Unix.
Què és PHP? → PHP: Hipertext Preprocessor
f(x) = x * f(x-1)
  • En un algorisme:
El càlcul del factorial d'un nombre es pot implementar amb un algorisme recursiu. En pseudocodi és:
FUNCIÓ F := FACTORIAL (SENCER:N)
SI N = 0
F := 1
SINÓ
F := N * FACTORIAL (N - 1)
FI_SI
FI_FUNCIÓ

És a dir: El factorial de zero val 1; per a nombres més grans que zero, el factorial del nombre és aquest mateix nombre multiplicat pel factorial del nombre sencer immediatament més petit.

Vegeu també

[modifica]

Referències

[modifica]

Enllaços externs

[modifica]
  • Dictionary of Algorithms and Data Structures del NIST (anglès)